Large Cross‐Free Sets in Steiner Triple Systems

A cross‐free set of size m in a Steiner triple system is three pairwise disjoint m‐element subsets such that no intersects all the three ‐s. We conjecture that for every admissible n there is an STS(n) with a cross‐free set of size which if true, is best possible. We prove this conjecture for the case , constructing an STS containing a cross‐free set of size 6k. We note that some of the 3‐bichromatic STSs, constructed by Colbourn, Dinitz, and Rosa, have cross‐free sets of size close to 6k (but cannot have size exactly 6k). The constructed STS shows that equality is possible for in the following result: in every 3‐coloring of the blocks of any Steiner triple system STS(n) there is a monochromatic connected component of size at least (we conjecture that equality holds for every admissible n). The analog problem can be asked for r‐colorings as well, if and is a prime power, we show that the answer is the same as in case of complete graphs: in every r‐coloring of the blocks of any STS(n), there is a monochromatic connected component with at least points, and this is sharp for infinitely many n.     

On some colorings of a double graph

In this note, we present some results concerning the chromatic index, the total chromatic index, the adjacent vertex distinguishing chromatic index and the adjacent vertex distinguishing total chromatic index for double graphs. In particular, we study the double graphs of class 1 and of type 1.     

Halin-图的邻强边染色

图G(V,E)的正常κ-边染色f叫做图G(V,E)的κ-邻强边染色当且仅当任意uv∈E(G)满足f[u]≠f[v],其中,f[u]={f(uw)|uw∈E(G)},称f是G的κ-临强边染色,简记为κ-ASEC.并且x′_as(G)=min{k|κ-ASEC of G}叫做G(V,E)的邻强边色数.本文研究了△(G)≥5的Halin-图的邻强边色数.     

Coloring plane graphs with independent crossings

We show that every plane graph with maximum face size four in which all faces of size four are vertex‐disjoint is cyclically 5‐colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 184–205, 2010     

Path coupling using stopping times and counting independent sets and colorings in hypergraphs

We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree Δ of a vertex and the minimum size m of an edge satisfy m ≥ 2Δ + 1. We also show that the Glauber dynamics for proper q‐colorings of a hypergraph mixes rapidly if m ≥ 4 and q > Δ, and if m = 3 and q ≥ 1.65Δ. We give related results on the hardness of exact and approximate counting for both problems. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008